package com.sujeet.learning.sort;

import java.util.ArrayList;

import java.util.Arrays;

import java.util.List;

public class Merge {

	public static void main(String[] args) {

		ArrayList<Integer> sample = new ArrayList<Integer>(Arrays.asList(10, 9,1, 2, 3, 11, 4, 5, 8));
		System.out.println("size: " + sample.size());
		sort(sample);

	}

	public static List<Integer> sort(List<Integer> sample) {

		if (sample.size() <= 1)	return sample;
		Integer midPoint = Math.round(sample.size() / 2);
		System.out.println(midPoint);
		List<Integer> a = sample.subList(0, midPoint);
		List<Integer> b = sample.subList(midPoint, sample.size());
		System.out.println(a);
		System.out.println(b);
		a = sort(a);
		b = sort(b);
		return merge(a, b);
	}

	public static List<Integer> merge(List<Integer> a, List<Integer> b) {

		System.out.println("merging a:" + a + " b: " + b);
		List<Integer> retVal = new ArrayList<Integer>();
		int first = 0;
		while (a.size() > 0 || b.size() > 0) {
			if (a.size() > 0 && b.size() > 0) {
				if (a.get(first) >= b.get(first)) {
					retVal.add(a.get(first));
					a = a.subList(first + 1, a.size());
				} else {
					retVal.add(b.get(first));
					b = b.subList(first + 1, b.size());
				}
			} else {
				if (a.size() > 0) {
					retVal.add(a.get(first));
					a = a.subList(first + 1, a.size());
				}
				if (b.size() > 0) {
					retVal.add(b.get(first));
					b = b.subList(first + 1, b.size());
				}
			}
		}
		System.out.println("merge result: " + retVal);
		return retVal;
	}

}
